The invention relates to a Maximum Likelihood Sequence Estimation (MLSE) algorithm, and more specifically to a method for improving the efficiency of a Viterbi algorithm in a system receiving a signal string.
Generally, the communication on a memory containing channel becomes more difficult due to unintentional analog convolution coding, which is due to the interaction between symbols. In this context the term "memory containing" means that the values of respective bits in a sequence or in a bit string in a digital transmission system depend on the bits preceding and/or succeeding the respective bit, i.e. on the "memory" of the system. A memory containing channel is intentionally constructed when utilizing convolution codes. The memory of the system is utilized to make the transmission more reliable.
Usually efforts are made to remove unintentional interaction on the transmission path, e.g. with linear or non-linear filtering, the receiver "seeing" a channel almost without memory.
A receiver for data transmission systems containing memory is in a known way based on a MLSE algorithm. With the aid of the MLSE algorithm such a sequence or a bit string is found, which with the greatest probability is the same as the transmitted sequence.
In an ideal MLSE algorithm a signal formed through all possible symbol strings (combinations of symbols or bits) is tested against the signal actually received. Thereby, it is assumed that the response of the channel is known and/or measured. It is possible to select the "best" symbol string with different criteria, which minimize the error probability of the decision.
The use of a MLSE algorithm is in practice limited by the fact that when the length of the symbol string increases, the number of possible combinations to be tested will increase exponentially.
Efforts have been made to solve this problem by taking into account the length of the channel, whereby the calculation requirements are exponentially proportional to the length of the channel instead of to the length of the sequence. The Viterbi algorithm is a well-known algorithm of this kind. As an example of a system where the MLSE-algorithm may be used, the pan-European GSM system may be mentioned, in which it is possible with the Viterbi algorithm to solve the coding for error correction and unintentional coding due to the radio transmission path. With the Viterbi algorithm it is possible to find efficiently the best possible symbol sequence or that sequence, at which the ideal MLSE algorithm also would arrive.
Known methods, that are less complicated than the complete MLSE and the Viterbi algorithm, have a disadvantage of poorer performance than the MLSE.
So called look-up algorithms are also known, with which the Viterbi algorithm can be extended so that it will be able to find the most probable sequence, and in addition a desired number of sequences in descending probability order can be found. As an example of a look-up algorithm of this type there may be mentioned Henry S. Thomson, "Active Chart Parsing/Best First Enumeration of Parts in a Lattice", European Conference on Speech Communication and Technology, Paris, September 1989.
On the other hand, in transmission systems it is known to use error monitoring or error detection to detect, and possibly to correct, an error in a received sequence. Several error detecting functions are known; they are generally of a block type and based on the use of a polynomial. A generic name for these is CRC (Cyclic Redundancy Check)--in colloquial language we talk about parity checks.